﻿<!DOCTYPE html>
<html class="theme theme-white">
<head>
<meta charset="utf-8">
<title>手写代码</title>
<link href="https://www.zybuluo.com/static/assets/template-theme-white.css" rel="stylesheet" media="screen">
<style type="text/css">

#wmd-preview h1  {
    color: #0077bb; /* 将标题改为蓝色 */
}</style>
</head>
<body class="theme theme-white">
<div id="wmd-preview" class="wmd-preview wmd-preview-full-reader"><div class="md-section-divider"></div><div class="md-section-divider"></div><h1 data-anchor-id="23sq" id="手写代码">手写代码</h1><p data-anchor-id="tzdd"><code>Java面试题</code></p><hr><div class="md-section-divider"></div><h3 data-anchor-id="rlab" id="singleton-单例模式">Singleton 单例模式</h3><ol data-anchor-id="8hkn">
<li>饿汉法</li>
</ol><p data-anchor-id="oqcq">顾名思义，饿汉法就是在第一次引用该类的时候就创建对象实例，而不管实际是否需要创建。代码如下：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="323s"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">     </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> instance </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">     </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">(){</span></code></li><li class="L3"><code><span class="pln">     </span><span class="pun">}</span></code></li><li class="L4"><code><span class="pln">     </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> getInstance</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">         </span><span class="kwd">return</span><span class="pln"> instance</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">     </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln"> </span><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="9nvt">这样做的好处是编写简单，但是无法做到延迟创建对象。</p><ol data-anchor-id="pl1l">
<li>懒汉式（非线程安全）</li>
</ol><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="nt94"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">      </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> instance</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">      </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">(){}</span><span class="pln"> </span></code></li><li class="L3"><code></code></li><li class="L4"><code><span class="pln">      </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> getInstance</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">          </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">instance </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">              instance </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">          </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">          </span><span class="kwd">return</span><span class="pln"> instance</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">      </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pln"> </span><span class="pun">}</span></code></li></ol></pre><ol data-anchor-id="x01d">
<li>懒汉式（线程安全）</li>
</ol><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="td19"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">      </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> instance</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">      </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">(){}</span></code></li><li class="L3"><code></code></li><li class="L4"><code><span class="pln">      </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">synchronized</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> getInstance</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">          </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">instance </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">              instance </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">          </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">          </span><span class="kwd">return</span><span class="pln"> instance</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">      </span><span class="pun">}</span></code></li><li class="L0"><code><span class="pln"> </span><span class="pun">}</span></code></li></ol></pre><ol data-anchor-id="s1nk">
<li>双重校验锁（DCL） </li>
</ol><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="6z83"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code><span class="pln">    </span><span class="com">/**</span></code></li><li class="L2"><code><span class="com">     * 注意此处使用的关键字 volatile，</span></code></li><li class="L3"><code><span class="com">     * 被volatile修饰的变量的值，将不会被本地线程缓存，</span></code></li><li class="L4"><code><span class="com">     * 所有对该变量的读写都是直接操作共享内存，从而确保多个线程能正确的处理该变量。</span></code></li><li class="L5"><code><span class="com">     */</span></code></li><li class="L6"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">volatile</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> singleton</span><span class="pun">;</span></code></li><li class="L7"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L8"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L9"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> getInstance</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L0"><code><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">instance </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code><span class="pln">            </span><span class="kwd">synchronized</span><span class="pun">(</span><span class="typ">Singleton</span><span class="pun">.</span><span class="kwd">class</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L2"><code><span class="pln">                </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">instance </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">                    instance </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">();</span></code></li><li class="L4"><code><span class="pln">                </span><span class="pun">}</span></code></li><li class="L5"><code><span class="pln">            </span><span class="pun">}</span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L7"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> singleton</span><span class="pun">;</span></code></li><li class="L8"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L9"><code><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="i86q">「双重校验锁」：既可以达到线程安全，也可以使性能不受很大的影响，换句话说在保证线程安全的前提下，既节省空间也节省了时间，集合了「饿汉式」和两种「懒汉式」的优点，取其精华，去其槽粕。</p><ol data-anchor-id="rcbn">
<li>静态内部类</li>
</ol><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="3lf4"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">(){</span></code></li><li class="L2"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L3"><code><span class="pln">      </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> getInstance</span><span class="pun">(){</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> </span><span class="typ">SingletonHolder</span><span class="pun">.</span><span class="pln">sInstance</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">SingletonHolder</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">        </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pln"> sInstance </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Singleton</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="gxif" id="消费者生产者">消费者生产者</h3><p data-anchor-id="vxio">生产者：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="m9fv"><ol class="linenums"><li class="L0"><code><span class="kwd">import</span><span class="pln"> java</span><span class="pun">.</span><span class="pln">util</span><span class="pun">.</span><span class="pln">concurrent</span><span class="pun">.</span><span class="typ">BlockingQueue</span><span class="pun">;</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="kwd">class</span><span class="pln"> </span><span class="typ">Producer</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Runnable</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">protected</span><span class="pln"> </span><span class="typ">BlockingQueue</span><span class="pun">&lt;</span><span class="typ">Object</span><span class="pun">&gt;</span><span class="pln"> queue</span><span class="pun">;</span></code></li><li class="L4"><code></code></li><li class="L5"><code><span class="pln">    </span><span class="typ">Producer</span><span class="pun">(</span><span class="typ">BlockingQueue</span><span class="pun">&lt;</span><span class="typ">Object</span><span class="pun">&gt;</span><span class="pln"> theQueue</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code><span class="pln">        </span><span class="kwd">this</span><span class="pun">.</span><span class="pln">queue </span><span class="pun">=</span><span class="pln"> theQueue</span><span class="pun">;</span></code></li><li class="L7"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L8"><code></code></li><li class="L9"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> run</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L0"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code><span class="pln">            </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">true</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L2"><code><span class="pln">                </span><span class="typ">Object</span><span class="pln"> justProduced </span><span class="pun">=</span><span class="pln"> getResource</span><span class="pun">();</span></code></li><li class="L3"><code><span class="pln">                queue</span><span class="pun">.</span><span class="pln">put</span><span class="pun">(</span><span class="pln">justProduced</span><span class="pun">);</span></code></li><li class="L4"><code><span class="pln">                </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"Produced resource - Queue size now = "</span></code></li><li class="L5"><code><span class="pln">                        </span><span class="pun">+</span><span class="pln"> queue</span><span class="pun">.</span><span class="pln">size</span><span class="pun">());</span></code></li><li class="L6"><code><span class="pln">            </span><span class="pun">}</span></code></li><li class="L7"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">InterruptedException</span><span class="pln"> ex</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L8"><code><span class="pln">            </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"Producer INTERRUPTED"</span><span class="pun">);</span></code></li><li class="L9"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L0"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="typ">Object</span><span class="pln"> getResource</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L4"><code><span class="pln">            </span><span class="typ">Thread</span><span class="pun">.</span><span class="pln">sleep</span><span class="pun">(</span><span class="lit">100</span><span class="pun">);</span><span class="pln"> </span><span class="com">// simulate time passing during read</span></code></li><li class="L5"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">InterruptedException</span><span class="pln"> ex</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code><span class="pln">            </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"Producer Read INTERRUPTED"</span><span class="pun">);</span></code></li><li class="L7"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L8"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Object</span><span class="pun">();</span></code></li><li class="L9"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L0"><code><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="ri6u">消费者:</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="yyjt"><ol class="linenums"><li class="L0"><code><span class="kwd">import</span><span class="pln"> java</span><span class="pun">.</span><span class="pln">util</span><span class="pun">.</span><span class="pln">concurrent</span><span class="pun">.</span><span class="typ">BlockingQueue</span><span class="pun">;</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="kwd">class</span><span class="pln"> </span><span class="typ">Consumer</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Runnable</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">protected</span><span class="pln"> </span><span class="typ">BlockingQueue</span><span class="pun">&lt;</span><span class="typ">Object</span><span class="pun">&gt;</span><span class="pln"> queue</span><span class="pun">;</span></code></li><li class="L4"><code></code></li><li class="L5"><code><span class="pln">    </span><span class="typ">Consumer</span><span class="pun">(</span><span class="typ">BlockingQueue</span><span class="pun">&lt;</span><span class="typ">Object</span><span class="pun">&gt;</span><span class="pln"> theQueue</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code><span class="pln">        </span><span class="kwd">this</span><span class="pun">.</span><span class="pln">queue </span><span class="pun">=</span><span class="pln"> theQueue</span><span class="pun">;</span></code></li><li class="L7"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L8"><code></code></li><li class="L9"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> run</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L0"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code><span class="pln">            </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">true</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L2"><code><span class="pln">                </span><span class="typ">Object</span><span class="pln"> obj </span><span class="pun">=</span><span class="pln"> queue</span><span class="pun">.</span><span class="pln">take</span><span class="pun">();</span></code></li><li class="L3"><code><span class="pln">                </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"Consumed resource - Queue size now = "</span></code></li><li class="L4"><code><span class="pln">                        </span><span class="pun">+</span><span class="pln"> queue</span><span class="pun">.</span><span class="pln">size</span><span class="pun">());</span></code></li><li class="L5"><code><span class="pln">                take</span><span class="pun">(</span><span class="pln">obj</span><span class="pun">);</span></code></li><li class="L6"><code><span class="pln">            </span><span class="pun">}</span></code></li><li class="L7"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">InterruptedException</span><span class="pln"> ex</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L8"><code><span class="pln">            </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"CONSUMER INTERRUPTED"</span><span class="pun">);</span></code></li><li class="L9"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L0"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">void</span><span class="pln"> take</span><span class="pun">(</span><span class="typ">Object</span><span class="pln"> obj</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L4"><code><span class="pln">            </span><span class="typ">Thread</span><span class="pun">.</span><span class="pln">sleep</span><span class="pun">(</span><span class="lit">100</span><span class="pun">);</span><span class="pln"> </span><span class="com">// simulate time passing</span></code></li><li class="L5"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">InterruptedException</span><span class="pln"> ex</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code><span class="pln">            </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"Consumer Read INTERRUPTED"</span><span class="pun">);</span></code></li><li class="L7"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L8"><code><span class="pln">        </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"Consuming object "</span><span class="pln"> </span><span class="pun">+</span><span class="pln"> obj</span><span class="pun">);</span></code></li><li class="L9"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L0"><code><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="bsly">测试该解决方案是否运行正常 : </p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="s5b0"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">import</span><span class="pln"> java</span><span class="pun">.</span><span class="pln">util</span><span class="pun">.</span><span class="pln">concurrent</span><span class="pun">.</span><span class="typ">BlockingQueue</span><span class="pun">;</span></code></li><li class="L1"><code class="language-java"><span class="kwd">import</span><span class="pln"> java</span><span class="pun">.</span><span class="pln">util</span><span class="pun">.</span><span class="pln">concurrent</span><span class="pun">.</span><span class="typ">LinkedBlockingQueue</span><span class="pun">;</span></code></li><li class="L2"><code class="language-java"></code></li><li class="L3"><code class="language-java"><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">ProducerConsumerExample</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L4"><code class="language-java"><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> main</span><span class="pun">(</span><span class="typ">String</span><span class="pun">[]</span><span class="pln"> args</span><span class="pun">)</span><span class="pln"> </span><span class="kwd">throws</span><span class="pln"> </span><span class="typ">InterruptedException</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L5"><code class="language-java"><span class="pln">        </span><span class="kwd">int</span><span class="pln"> numProducers </span><span class="pun">=</span><span class="pln"> </span><span class="lit">4</span><span class="pun">;</span></code></li><li class="L6"><code class="language-java"><span class="pln">        </span><span class="kwd">int</span><span class="pln"> numConsumers </span><span class="pun">=</span><span class="pln"> </span><span class="lit">3</span><span class="pun">;</span></code></li><li class="L7"><code class="language-java"></code></li><li class="L8"><code class="language-java"><span class="pln">        </span><span class="typ">BlockingQueue</span><span class="pun">&lt;</span><span class="typ">Object</span><span class="pun">&gt;</span><span class="pln"> myQueue </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">LinkedBlockingQueue</span><span class="pun">&lt;&gt;(</span><span class="lit">20</span><span class="pun">);</span></code></li><li class="L9"><code class="language-java"></code></li><li class="L0"><code class="language-java"><span class="pln">        </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> numProducers</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code class="language-java"><span class="pln">            </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Thread</span><span class="pun">(</span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Producer</span><span class="pun">(</span><span class="pln">myQueue</span><span class="pun">)).</span><span class="pln">start</span><span class="pun">();</span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L3"><code class="language-java"></code></li><li class="L4"><code class="language-java"><span class="pln">        </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> numConsumers</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L5"><code class="language-java"><span class="pln">            </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Thread</span><span class="pun">(</span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Consumer</span><span class="pun">(</span><span class="pln">myQueue</span><span class="pun">)).</span><span class="pln">start</span><span class="pun">();</span></code></li><li class="L6"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L7"><code class="language-java"></code></li><li class="L8"><code class="language-java"><span class="pln">        </span><span class="com">// Let the simulation run for, say, 10 seconds</span></code></li><li class="L9"><code class="language-java"><span class="pln">        </span><span class="typ">Thread</span><span class="pun">.</span><span class="pln">sleep</span><span class="pun">(</span><span class="lit">10</span><span class="pln"> </span><span class="pun">*</span><span class="pln"> </span><span class="lit">1000</span><span class="pun">);</span></code></li><li class="L0"><code class="language-java"></code></li><li class="L1"><code class="language-java"><span class="pln">        </span><span class="com">// End of simulation - shut down gracefully</span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="typ">System</span><span class="pun">.</span><span class="pln">exit</span><span class="pun">(</span><span class="lit">0</span><span class="pun">);</span></code></li><li class="L3"><code class="language-java"><span class="pln">    </span><span class="pun">}</span></code></li><li class="L4"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="vhaz" id="序列化">序列化</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="rb8q"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Box</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Serializable</span><span class="pun">{</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> width</span><span class="pun">;</span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> height</span><span class="pun">;</span></code></li><li class="L4"><code></code></li><li class="L5"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">Box</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> width</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> height</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code><span class="pln">        </span><span class="kwd">this</span><span class="pun">.</span><span class="pln">width </span><span class="pun">=</span><span class="pln"> width</span><span class="pun">;</span></code></li><li class="L7"><code><span class="pln">        </span><span class="kwd">this</span><span class="pun">.</span><span class="pln">height </span><span class="pun">=</span><span class="pln"> height</span><span class="pun">;</span></code></li><li class="L8"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L9"><code></code></li><li class="L0"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> getWidth</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> width</span><span class="pun">;</span></code></li><li class="L2"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L3"><code></code></li><li class="L4"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> setWidth</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> width</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L5"><code><span class="pln">        </span><span class="kwd">this</span><span class="pun">.</span><span class="pln">width </span><span class="pun">=</span><span class="pln"> width</span><span class="pun">;</span></code></li><li class="L6"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L7"><code></code></li><li class="L8"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> getHeight</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L9"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> height</span><span class="pun">;</span></code></li><li class="L0"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> setHeight</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> height</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">        </span><span class="kwd">this</span><span class="pun">.</span><span class="pln">height </span><span class="pun">=</span><span class="pln"> height</span><span class="pun">;</span></code></li><li class="L4"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L5"><code></code></li><li class="L6"><code><span class="pln">    </span><span class="lit">@Override</span></code></li><li class="L7"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">String</span><span class="pln"> toString</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L8"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> </span><span class="str">"Child{"</span><span class="pln"> </span><span class="pun">+</span></code></li><li class="L9"><code><span class="pln">                </span><span class="str">"width="</span><span class="pln"> </span><span class="pun">+</span><span class="pln"> width </span><span class="pun">+</span></code></li><li class="L0"><code><span class="pln">                </span><span class="str">", height="</span><span class="pln"> </span><span class="pun">+</span><span class="pln"> height </span><span class="pun">+</span></code></li><li class="L1"><code><span class="pln">                </span><span class="str">'}'</span><span class="pun">;</span></code></li><li class="L2"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L3"><code><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="qbha"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">SerializableTest</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> main</span><span class="pun">(</span><span class="typ">String</span><span class="pln"> args</span><span class="pun">[])</span><span class="pln"> </span><span class="kwd">throws</span><span class="pln"> </span><span class="typ">Exception</span><span class="pun">{</span></code></li><li class="L3"><code></code></li><li class="L4"><code><span class="pln">        </span><span class="typ">File</span><span class="pln"> file </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">File</span><span class="pun">(</span><span class="str">"box.out"</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L5"><code></code></li><li class="L6"><code><span class="pln">        </span><span class="typ">FileOutputStream</span><span class="pln"> fos </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">FileOutputStream</span><span class="pun">(</span><span class="pln">file</span><span class="pun">);</span></code></li><li class="L7"><code><span class="pln">        </span><span class="typ">ObjectOutputStream</span><span class="pln"> </span><span class="kwd">out</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ObjectOutputStream</span><span class="pun">(</span><span class="pln">fos</span><span class="pun">);</span></code></li><li class="L8"><code><span class="pln">        </span><span class="typ">Box</span><span class="pln"> oldBox </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Box</span><span class="pun">(</span><span class="lit">10</span><span class="pun">,</span><span class="lit">20</span><span class="pun">);</span></code></li><li class="L9"><code><span class="pln">        </span><span class="kwd">out</span><span class="pun">.</span><span class="pln">writeObject</span><span class="pun">(</span><span class="pln">oldBox</span><span class="pun">);</span></code></li><li class="L0"><code><span class="pln">        </span><span class="kwd">out</span><span class="pun">.</span><span class="pln">close</span><span class="pun">();</span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">        </span><span class="typ">FileInputStream</span><span class="pln"> fis </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">FileInputStream</span><span class="pun">(</span><span class="pln">file</span><span class="pun">);</span></code></li><li class="L3"><code><span class="pln">        </span><span class="typ">ObjectInputStream</span><span class="pln"> </span><span class="kwd">in</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ObjectInputStream</span><span class="pun">(</span><span class="pln">fis</span><span class="pun">);</span></code></li><li class="L4"><code><span class="pln">        </span><span class="typ">Box</span><span class="pln"> newBox </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="typ">Box</span><span class="pun">)</span><span class="kwd">in</span><span class="pun">.</span><span class="pln">readObject</span><span class="pun">();</span></code></li><li class="L5"><code><span class="pln">        </span><span class="kwd">in</span><span class="pun">.</span><span class="pln">close</span><span class="pun">();</span></code></li><li class="L6"><code><span class="pln">        </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="pln">newBox</span><span class="pun">.</span><span class="pln">toString</span><span class="pun">());</span></code></li><li class="L7"><code></code></li><li class="L8"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L9"><code><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="03q4" id="克隆">克隆</h3><p data-anchor-id="pmgd">浅度克隆 :</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="atf7"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Product</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Cloneable</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">String</span><span class="pln"> name</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L2"><code></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">Object</span><span class="pln"> clone</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L4"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L5"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">super</span><span class="pun">.</span><span class="pln">clone</span><span class="pun">();</span><span class="pln">   </span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">CloneNotSupportedException</span><span class="pln"> e</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L7"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L8"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L9"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L0"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="dz85">深度克隆 : </p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="zsr5"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Attribute</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Cloneable</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">String</span><span class="pln"> </span><span class="kwd">no</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L2"><code></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">Object</span><span class="pln"> clone</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L4"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L5"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">super</span><span class="pun">.</span><span class="pln">clone</span><span class="pun">();</span><span class="pln">   </span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">CloneNotSupportedException</span><span class="pln"> e</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L7"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L8"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L9"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L0"><code><span class="pun">}</span><span class="pln">   </span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Product</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Cloneable</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">String</span><span class="pln"> name</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L4"><code></code></li><li class="L5"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Attribute</span><span class="pln"> attribute</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L6"><code></code></li><li class="L7"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">Object</span><span class="pln"> clone</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L8"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L9"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">super</span><span class="pun">.</span><span class="pln">clone</span><span class="pun">();</span><span class="pln">   </span></code></li><li class="L0"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">CloneNotSupportedException</span><span class="pln"> e</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L2"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L3"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L4"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="ndhk">使用对象序列化和反序列化实现深度克隆 : </p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="2iqs"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Attribute</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">String</span><span class="pln"> </span><span class="kwd">no</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L2"><code><span class="pun">}</span><span class="pln">   </span></code></li><li class="L3"><code></code></li><li class="L4"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Product</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L5"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">String</span><span class="pln"> name</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L6"><code></code></li><li class="L7"><code><span class="pln">    </span><span class="kwd">private</span><span class="pln"> </span><span class="typ">Attribute</span><span class="pln"> attribute</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L8"><code></code></li><li class="L9"><code><span class="pln">    </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">Product</span><span class="pln"> clone</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L0"><code><span class="pln">        </span><span class="typ">ByteArrayOutputStream</span><span class="pln"> byteOut </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">        </span><span class="typ">ObjectOutputStream</span><span class="pln"> objOut </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L2"><code><span class="pln">        </span><span class="typ">ByteArrayInputStream</span><span class="pln"> byteIn </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L3"><code><span class="pln">        </span><span class="typ">ObjectInputStream</span><span class="pln"> objIn </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L4"><code></code></li><li class="L5"><code><span class="pln">        </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L6"><code><span class="pln">            byteOut </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ByteArrayOutputStream</span><span class="pun">();</span><span class="pln">    </span></code></li><li class="L7"><code><span class="pln">            objOut </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ObjectOutputStream</span><span class="pun">(</span><span class="pln">byteOut</span><span class="pun">);</span><span class="pln">    </span></code></li><li class="L8"><code><span class="pln">            objOut</span><span class="pun">.</span><span class="pln">writeObject</span><span class="pun">(</span><span class="pln">prototype</span><span class="pun">);</span><span class="pln">   </span></code></li><li class="L9"><code></code></li><li class="L0"><code><span class="pln">            byteIn </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ByteArrayInputStream</span><span class="pun">(</span><span class="pln">byteOut</span><span class="pun">.</span><span class="pln">toByteArray</span><span class="pun">());</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">            objIn </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ObjectInputStream</span><span class="pun">(</span><span class="pln">byteIn</span><span class="pun">);</span><span class="pln">   </span></code></li><li class="L2"><code></code></li><li class="L3"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">(</span><span class="typ">ContretePrototype</span><span class="pun">)</span><span class="pln"> objIn</span><span class="pun">.</span><span class="pln">readObject</span><span class="pun">();</span><span class="pln">   </span></code></li><li class="L4"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">IOException</span><span class="pln"> e</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L5"><code><span class="pln">            </span><span class="kwd">throw</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">RuntimeException</span><span class="pun">(</span><span class="str">"Clone Object failed in IO."</span><span class="pun">,</span><span class="pln">e</span><span class="pun">);</span><span class="pln">      </span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">ClassNotFoundException</span><span class="pln"> e</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L7"><code><span class="pln">            </span><span class="kwd">throw</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">RuntimeException</span><span class="pun">(</span><span class="str">"Class not found."</span><span class="pun">,</span><span class="pln">e</span><span class="pun">);</span><span class="pln">      </span></code></li><li class="L8"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">finally</span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L9"><code><span class="pln">            </span><span class="kwd">try</span><span class="pun">{</span><span class="pln">   </span></code></li><li class="L0"><code><span class="pln">                byteIn </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L1"><code><span class="pln">                byteOut </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln">   </span></code></li><li class="L2"><code><span class="pln">                </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">objOut </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> objOut</span><span class="pun">.</span><span class="pln">close</span><span class="pun">();</span><span class="pln">      </span></code></li><li class="L3"><code><span class="pln">                </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">objIn </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> objIn</span><span class="pun">.</span><span class="pln">close</span><span class="pun">();</span><span class="pln">      </span></code></li><li class="L4"><code><span class="pln">            </span><span class="pun">}</span><span class="kwd">catch</span><span class="pun">(</span><span class="typ">IOException</span><span class="pln"> e</span><span class="pun">){</span><span class="pln">      </span></code></li><li class="L5"><code><span class="pln">            </span><span class="pun">}</span><span class="pln">      </span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L7"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">   </span></code></li><li class="L8"><code><span class="pun">}</span><span class="pln"> </span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="5bfr" id="选择排序">选择排序</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="l1x3"><ol class="linenums"><li class="L0"><code class="language-java"><span class="com">/**</span></code></li><li class="L1"><code class="language-java"><span class="com"> * 选择排序算法</span></code></li><li class="L2"><code class="language-java"><span class="com"> * 在未排序序列中找到最小元素，存放到排序序列的起始位置  </span></code></li><li class="L3"><code class="language-java"><span class="com"> * 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。 </span></code></li><li class="L4"><code class="language-java"><span class="com"> * 以此类推，直到所有元素均排序完毕。 </span></code></li><li class="L5"><code class="language-java"><span class="com"> * @param numbers</span></code></li><li class="L6"><code class="language-java"><span class="com"> */</span></code></li><li class="L7"><code class="language-java"><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> selectSort</span><span class="pun">(</span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> numbers</span><span class="pun">){</span></code></li><li class="L8"><code class="language-java"><span class="pln">    </span><span class="kwd">int</span><span class="pln"> size </span><span class="pun">=</span><span class="pln"> numbers</span><span class="pun">.</span><span class="pln">length</span><span class="pun">;</span><span class="pln"> </span><span class="com">//数组长度</span></code></li><li class="L9"><code class="language-java"><span class="pln">    </span><span class="kwd">int</span><span class="pln"> temp </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">;</span><span class="pln"> </span><span class="com">//中间变量</span></code></li><li class="L0"><code class="language-java"></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="kwd">for</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> size </span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++){</span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="kwd">int</span><span class="pln"> k </span><span class="pun">=</span><span class="pln"> i</span><span class="pun">;</span><span class="pln">   </span><span class="com">//待确定的位置</span></code></li><li class="L3"><code class="language-java"><span class="pln">        </span><span class="com">//选择出应该在第i个位置的数</span></code></li><li class="L4"><code class="language-java"><span class="pln">        </span><span class="kwd">for</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> j </span><span class="pun">=</span><span class="pln"> size </span><span class="pun">-</span><span class="lit">1</span><span class="pln"> </span><span class="pun">;</span><span class="pln"> j </span><span class="pun">&gt;</span><span class="pln"> i </span><span class="pun">;</span><span class="pln"> j</span><span class="pun">--){</span></code></li><li class="L5"><code class="language-java"><span class="pln">            </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">numbers</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">&lt;</span><span class="pln"> numbers</span><span class="pun">[</span><span class="pln">k</span><span class="pun">]){</span></code></li><li class="L6"><code class="language-java"><span class="pln">                k </span><span class="pun">=</span><span class="pln"> j</span><span class="pun">;</span></code></li><li class="L7"><code class="language-java"><span class="pln">            </span><span class="pun">}</span></code></li><li class="L8"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L9"><code class="language-java"><span class="pln">        </span><span class="com">//交换两个数</span></code></li><li class="L0"><code class="language-java"><span class="pln">        temp </span><span class="pun">=</span><span class="pln"> numbers</span><span class="pun">[</span><span class="pln">i</span><span class="pun">];</span></code></li><li class="L1"><code class="language-java"><span class="pln">        numbers</span><span class="pun">[</span><span class="pln">i</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> numbers</span><span class="pun">[</span><span class="pln">k</span><span class="pun">];</span></code></li><li class="L2"><code class="language-java"><span class="pln">        numbers</span><span class="pun">[</span><span class="pln">k</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> temp</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pln">    </span><span class="pun">}</span></code></li><li class="L4"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="61np" id="插入排序">插入排序</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="5m8y"><ol class="linenums"><li class="L0"><code><span class="com">/**  </span></code></li><li class="L1"><code><span class="com"> * 插入排序</span></code></li><li class="L2"><code><span class="com"> * </span></code></li><li class="L3"><code><span class="com"> * 从第一个元素开始，该元素可以认为已经被排序</span></code></li><li class="L4"><code><span class="com"> * 取出下一个元素，在已经排序的元素序列中从后向前扫描 </span></code></li><li class="L5"><code><span class="com"> * 如果该元素（已排序）大于新元素，将该元素移到下一位置  </span></code></li><li class="L6"><code><span class="com"> * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置  </span></code></li><li class="L7"><code><span class="com"> * 将新元素插入到该位置中  </span></code></li><li class="L8"><code><span class="com"> * 重复步骤2  </span></code></li><li class="L9"><code><span class="com"> * @param numbers  待排序数组</span></code></li><li class="L0"><code><span class="com"> */</span><span class="pln">  </span></code></li><li class="L1"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> insertSort</span><span class="pun">(</span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> numbers</span><span class="pun">){</span></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> size </span><span class="pun">=</span><span class="pln"> numbers</span><span class="pun">.</span><span class="pln">length</span><span class="pun">;</span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> temp </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">;</span></code></li><li class="L4"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> j </span><span class="pun">=</span><span class="pln">  </span><span class="lit">0</span><span class="pun">;</span></code></li><li class="L5"><code></code></li><li class="L6"><code><span class="pln">    </span><span class="kwd">for</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> size </span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++){</span></code></li><li class="L7"><code><span class="pln">        temp </span><span class="pun">=</span><span class="pln"> numbers</span><span class="pun">[</span><span class="pln">i</span><span class="pun">];</span></code></li><li class="L8"><code><span class="pln">        </span><span class="com">//假如temp比前面的值小，则将前面的值后移</span></code></li><li class="L9"><code><span class="pln">        </span><span class="kwd">for</span><span class="pun">(</span><span class="pln">j </span><span class="pun">=</span><span class="pln"> i </span><span class="pun">;</span><span class="pln"> j </span><span class="pun">&gt;</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> temp </span><span class="pun">&lt;</span><span class="pln"> numbers</span><span class="pun">[</span><span class="pln">j</span><span class="pun">-</span><span class="lit">1</span><span class="pun">]</span><span class="pln"> </span><span class="pun">;</span><span class="pln"> j </span><span class="pun">--){</span></code></li><li class="L0"><code><span class="pln">        numbers</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> numbers</span><span class="pun">[</span><span class="pln">j</span><span class="pun">-</span><span class="lit">1</span><span class="pun">];</span></code></li><li class="L1"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L2"><code><span class="pln">        numbers</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> temp</span><span class="pun">;</span></code></li><li class="L3"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L4"><code><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="eh6j" id="二分查找">二分查找</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="ew8n"><ol class="linenums"><li class="L0"><code><span class="com">/** </span></code></li><li class="L1"><code><span class="com"> * 二分查找又称折半查找，它是一种效率较高的查找方法。 【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 </span></code></li><li class="L2"><code><span class="com"> *  </span></code></li><li class="L3"><code><span class="com"> * @param array </span></code></li><li class="L4"><code><span class="com"> *            有序数组 * </span></code></li><li class="L5"><code><span class="com"> * @param searchKey </span></code></li><li class="L6"><code><span class="com"> *            查找元素 * </span></code></li><li class="L7"><code><span class="com"> * @return searchKey的数组下标，没找到返回-1 </span></code></li><li class="L8"><code><span class="com"> */</span><span class="pln">  </span></code></li><li class="L9"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> binarySearch</span><span class="pun">(</span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> array</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> searchKey</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">     </span><span class="kwd">int</span><span class="pln"> low </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> high </span><span class="pun">=</span><span class="pln"> array</span><span class="pun">.</span><span class="pln">length </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="pln">low </span><span class="pun">&lt;=</span><span class="pln"> high</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">        </span><span class="kwd">int</span><span class="pln"> middle </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">low </span><span class="pun">+</span><span class="pln"> high</span><span class="pun">)</span><span class="pln"> </span><span class="pun">/</span><span class="pln"> </span><span class="lit">2</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">searchKey </span><span class="pun">==</span><span class="pln"> array</span><span class="pun">[</span><span class="pln">middle</span><span class="pun">])</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">            </span><span class="kwd">return</span><span class="pln"> middle</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">searchKey </span><span class="pun">&lt;</span><span class="pln"> array</span><span class="pun">[</span><span class="pln">middle</span><span class="pun">])</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">            high </span><span class="pun">=</span><span class="pln"> middle </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">        </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">            low </span><span class="pun">=</span><span class="pln"> middle </span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="2rke" id="分块查找">分块查找</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="bv7t"><ol class="linenums"><li class="L0"><code><span class="com">/**</span></code></li><li class="L1"><code><span class="com"> * 分块查找</span></code></li><li class="L2"><code><span class="com"> * </span></code></li><li class="L3"><code><span class="com"> * @param index</span></code></li><li class="L4"><code><span class="com"> *            索引表，其中放的是各块的最大值</span></code></li><li class="L5"><code><span class="com"> * @param st</span></code></li><li class="L6"><code><span class="com"> *            顺序表，</span></code></li><li class="L7"><code><span class="com"> * @param key</span></code></li><li class="L8"><code><span class="com"> *            要查找的值</span></code></li><li class="L9"><code><span class="com"> * @param m</span></code></li><li class="L0"><code><span class="com"> *            顺序表中各块的长度相等，为m</span></code></li><li class="L1"><code><span class="com"> * @return</span></code></li><li class="L2"><code><span class="com"> */</span></code></li><li class="L3"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> blockSearch</span><span class="pun">(</span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> index</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> st</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> key</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> m</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L4"><code><span class="pln">    </span><span class="com">// 在序列st数组中，用分块查找方法查找关键字为key的记录</span></code></li><li class="L5"><code><span class="pln">    </span><span class="com">// 1.在index[ ] 中折半查找，确定要查找的key属于哪个块中</span></code></li><li class="L6"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> binarySearch</span><span class="pun">(</span><span class="pln">index</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">);</span></code></li><li class="L7"><code><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">i </span><span class="pun">&gt;=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L8"><code><span class="pln">        </span><span class="kwd">int</span><span class="pln"> j </span><span class="pun">=</span><span class="pln"> i </span><span class="pun">&gt;</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">?</span><span class="pln"> i </span><span class="pun">*</span><span class="pln"> m </span><span class="pun">:</span><span class="pln"> i</span><span class="pun">;</span></code></li><li class="L9"><code><span class="pln">        </span><span class="kwd">int</span><span class="pln"> len </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">i </span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="pun">*</span><span class="pln"> m</span><span class="pun">;</span></code></li><li class="L0"><code><span class="pln">        </span><span class="com">// 在确定的块中用顺序查找方法查找key</span></code></li><li class="L1"><code><span class="pln">        </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> k </span><span class="pun">=</span><span class="pln"> j</span><span class="pun">;</span><span class="pln"> k </span><span class="pun">&lt;</span><span class="pln"> len</span><span class="pun">;</span><span class="pln"> k</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L2"><code><span class="pln">            </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">key </span><span class="pun">==</span><span class="pln"> st</span><span class="pun">[</span><span class="pln">k</span><span class="pun">])</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L3"><code><span class="pln">                </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"查询成功"</span><span class="pun">);</span></code></li><li class="L4"><code><span class="pln">                </span><span class="kwd">return</span><span class="pln"> k</span><span class="pun">;</span></code></li><li class="L5"><code><span class="pln">            </span><span class="pun">}</span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span></code></li><li class="L7"><code><span class="pln">    </span><span class="pun">}</span></code></li><li class="L8"><code><span class="pln">    </span><span class="typ">System</span><span class="pun">.</span><span class="kwd">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="str">"查找失败"</span><span class="pun">);</span></code></li><li class="L9"><code><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span></code></li><li class="L0"><code><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="acw0" id="哈希查找">哈希查找</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="dac2"><ol class="linenums"><li class="L0"><code><span class="com">/**** </span></code></li><li class="L1"><code><span class="com"> * Hash查找 </span></code></li><li class="L2"><code><span class="com"> *  </span></code></li><li class="L3"><code><span class="com"> * @param hash </span></code></li><li class="L4"><code><span class="com"> * @param hashLength </span></code></li><li class="L5"><code><span class="com"> * @param key </span></code></li><li class="L6"><code><span class="com"> * @return </span></code></li><li class="L7"><code><span class="com"> */</span><span class="pln">  </span></code></li><li class="L8"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> searchHash</span><span class="pun">(</span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> hash</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> hashLength</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">    </span><span class="com">// 哈希函数  </span></code></li><li class="L0"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> hashAddress </span><span class="pun">=</span><span class="pln"> key </span><span class="pun">%</span><span class="pln"> hashLength</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="com">// 指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决  </span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="pln">hash</span><span class="pun">[</span><span class="pln">hashAddress</span><span class="pun">]</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> hash</span><span class="pun">[</span><span class="pln">hashAddress</span><span class="pun">]</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">        hashAddress </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(++</span><span class="pln">hashAddress</span><span class="pun">)</span><span class="pln"> </span><span class="pun">%</span><span class="pln"> hashLength</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L6"><code></code></li><li class="L7"><code><span class="pln">    </span><span class="com">// 查找到了开放单元，表示查找失败  </span></code></li><li class="L8"><code><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">hash</span><span class="pun">[</span><span class="pln">hashAddress</span><span class="pun">]</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pln">    </span><span class="kwd">return</span><span class="pln"> hashAddress</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pun">}</span><span class="pln">  </span></code></li><li class="L3"><code></code></li><li class="L4"><code><span class="com">/*** </span></code></li><li class="L5"><code><span class="com"> * 数据插入Hash表 </span></code></li><li class="L6"><code><span class="com"> *  </span></code></li><li class="L7"><code><span class="com"> * @param hash </span></code></li><li class="L8"><code><span class="com"> *            哈希表 </span></code></li><li class="L9"><code><span class="com"> * @param hashLength </span></code></li><li class="L0"><code><span class="com"> * @param data </span></code></li><li class="L1"><code><span class="com"> */</span><span class="pln">  </span></code></li><li class="L2"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> insertHash</span><span class="pun">(</span><span class="kwd">int</span><span class="pun">[]</span><span class="pln"> hash</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> hashLength</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> data</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">    </span><span class="com">// 哈希函数  </span></code></li><li class="L4"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> hashAddress </span><span class="pun">=</span><span class="pln"> data </span><span class="pun">%</span><span class="pln"> hashLength</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L5"><code></code></li><li class="L6"><code><span class="pln">    </span><span class="com">// 如果key存在，则说明已经被别人占用，此时必须解决冲突  </span></code></li><li class="L7"><code><span class="pln">    </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="pln">hash</span><span class="pun">[</span><span class="pln">hashAddress</span><span class="pun">]</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">        </span><span class="com">// 用开放寻址法找到  </span></code></li><li class="L9"><code><span class="pln">        hashAddress </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(++</span><span class="pln">hashAddress</span><span class="pun">)</span><span class="pln"> </span><span class="pun">%</span><span class="pln"> hashLength</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L1"><code></code></li><li class="L2"><code><span class="pln">    </span><span class="com">// 将data存入字典中  </span></code></li><li class="L3"><code><span class="pln">    hash</span><span class="pun">[</span><span class="pln">hashAddress</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> data</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="c46i" id="结束">结束</h3></div>
</body>
</html>